package cxydmmszl.chapter09.t155;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 最大的 leftMax 与 rightMax 之差的绝对值
 * <li style="color: green;">Desc</li>
 * 给定一个长度为 N(N>1) 的整形数组 arr, 可以划分成左右两个部分，左部分为 arr[0…K]，
 * 右部分为 arr[K+1…N-1]，K 可以取值的范围是 [0,N-2]。
 * 求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值中，最大是多少。
 * <br/><br/>[要求]<br/>
 * 时间复杂度为 O(n)，空间复杂度为 O(n)
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^6<br/>
 * 1⩽arr[i]⩽10^9
 * <li style="color: green;">Input</li>
 * 第一行一个整数 N，表示数组长度。<br/>
 * 接下来一行 N 个整数，表示数组内的数。
 * <li style="color: green;">Output</li>
 * 输出一个整数表示最优答案
 * <li style="color: blue;">Link</li> CD63
 *
 * @author habitplus
 * @since 2021-10-31 21:55
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            throw new RuntimeException("Input is invalid!");
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        int ans = maxDifference(arr);
        System.out.println(ans);
    }

    private static int maxDifference(int[] arr) {
        if (arr == null || arr.length < 2) return 0;

        int n = arr.length;
        int[] rightMax = new int[n];
        rightMax[n - 1] = arr[n - 1];
        for (int i = n - 2; i > 0; i--) {
            rightMax[i] = Math.max(arr[i], rightMax[i + 1]);
        }

        int res = 0;
        int leftMax = arr[0];
        for (int i = 0; i < n - 1; i++) {
            leftMax = Math.max(leftMax, arr[i]);
            res = Math.max(res, Math.abs(leftMax - rightMax[i+1]));
        }
        return res;
    }
}
